package com.wenhao.leetcode.medium;

/**
 * 题目：https://leetcode-cn.com/problems/jump-game-ii/
 * 跳跃游戏2
 *
 * @author Wenhao Tong
 * @Description
 * @create 2021-06-28 18:54
 */
public class LeetCode45 {

    public static void main(String[] args) {
        LeetCode45 leetCode45 = new LeetCode45();
        int jump = leetCode45.jump2(new int[]{2,3,0,1,4});
        System.out.println(jump);
    }

    /**
     * 最普通的动态规划解法
     * 复杂度是所有的数字求和
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        int[] step = new int[nums.length];
        for (int i = 0;i < nums.length;i++) {
            for (int j = 1;j <= nums[i] && i + j < nums.length;j++) {

                step[i + j] = (step[i + j] == 0 || step[i] + 1 < step[i + j]) ? step[i] + 1 : step[i + j];
            }
        }
        return step[nums.length - 1];
    }

    /**
     * 维护一个数组，里面储存的是当前节点可以到达的最远位置
     * @param nums
     * @return
     */
    public int jump2(int[] nums) {
        int reach = 0;
        int step = 0;
        int lastReach = 0;
        for (int i = 0;i < nums.length - 1;i++) {
            reach = reach > i + nums[i] ? reach : i + nums[i];
            // 超过了step - 1能够到达的最远距离，所以需要更新为step步能够到达的最远距离，同时步数也更新为step步
            if (i == lastReach) {
                lastReach = reach;
                step++;
            }
        }
        return step;
    }


}
